package cn.michael.dev.demo;

import java.util.HashMap;

/**
 * Created by hufenggang on 2021/11/2.
 */
public class LRUCache {
    // 缓存容器
    private HashMap<Integer, DoubleLinkedNode> cache = new HashMap<>();
    // 容器的容量大小
    private int capacity;
    // 容器内元素个数
    private int size;
    private DoubleLinkedNode head, tail;

    /**
     * 初始化容器
     *
     * @param capacity
     */
    public LRUCache(int capacity) {
        this.capacity = capacity;
        size = 0;
        head = new DoubleLinkedNode();
        tail = new DoubleLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 获取元素
     *
     * @param key
     * @return
     */
    public int get(int key) {
        DoubleLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        } else {
            // 将最新查询的数据移动到
            moveToHead(node);
            return node.value;
        }
    }

    /**
     * 写入元素到容器
     *
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        DoubleLinkedNode node = cache.get(key);

        if (node == null) {
            // 如果key不存在，则创建一个新的节点
            DoubleLinkedNode doubleLinkedNode = new DoubleLinkedNode(key, value);
            // 添加进Map
            cache.put(key, doubleLinkedNode);
            // 添加到双向链表的头部
            addToHead(node);
            size++;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DoubleLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                size--;
            }
        } else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    /**
     * 删除链表尾部元素
     *
     * @return
     */
    private DoubleLinkedNode removeTail() {
        DoubleLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }

    /**
     * 将节点移动到链表头部
     *
     * @param node
     */
    private void moveToHead(DoubleLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    /**
     * 添加到链表头部
     *
     * @param node
     */
    private void addToHead(DoubleLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    /**
     * 删除节点
     *
     * @param node
     */
    private void removeNode(DoubleLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /**
     * 双向循环链表
     */
    private class DoubleLinkedNode {
        int key;
        int value;
        DoubleLinkedNode prev;
        DoubleLinkedNode next;

        public DoubleLinkedNode() {
        }

        public DoubleLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}
